package com.algorithm.base.greedy;

import org.springframework.stereotype.Service;

import java.util.Arrays;

/**
 * 1005. K 次取反后最大化的数组和
 *
 * @author Amadeus
 * @date 2023/11/22
 */
@Service
public class LargestSumAfterKNegations {

    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int sum = 0;
        int out = 0;
        int min = Math.abs(nums[0]);
        for (int num : nums) {
            sum += num;
            if (num < 0) {
                out++;
            }
            min = Math.min(Math.abs(num), min);
        }
        if (k % 2 == 0 && nums[0] >= 0) {
            return sum;
        }

        if (out >= k) {
            for (int i = 0; i < k; i++) {
                sum += -2 * nums[i];
            }
        } else {
            int flag = (k - out) % 2;
            for (int i = 0; i < out; i++) {
                sum += -2 * nums[i];
            }
            if (flag > 0) {
                sum -= 2 * min;
            }
        }
        return sum;

    }

}
